package com.android.leetcode;

/**
 * 14. 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * <p>
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 * 这个题目迭代得我很反感
 * 字符          数值
 * I             1
 * V             5
 * X             10
 * L             50
 * C             100
 * D             500
 * M             1000
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/integer-to-roman
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution14 {

    public static void main(String[] args) {
        String result = intToRoman(3);
        System.out.println(result);
        int result1 = romanToInt("MCMXCIV");
        System.out.println(result1);
        String[] s = new String[]{"flower", "flow", "flight"};
        String result2 = longestCommonPrefix(s);
        System.out.println(result2);

    }

    public static String longestCommonPrefix(String[] strs) {

        for (int i = 0; i < strs.length; i++) {
            String s = strs[i];
            for (int i1 = 0; i1 < s.length(); i1++) {

            }
        }

        return "";
    }

    public static int romanToInt(String s) {
        String[] display = new String[]{"M", "D", "C", "L", "X", "V", "I"};
        int[] nums = new int[]{1000, 500, 100, 50, 10, 5, 1};
        int[] specialNums = new int[]{900, 400, 90, 40, 9, 4};
        int result = 0;
        int index = display.length - 1;
        for (int i = s.length() - 1; i >= 0; i--) {
            String current = String.valueOf(s.charAt(i));
            String next = "";
            if (i != 0) {
                next = String.valueOf(s.charAt(i - 1));
            }
            for (int i1 = index; i1 >= 0; i1--) {
                if (current.equals(display[i1])) {
                    index = i1;
                    if (current.equals("M") && next.equals("C")) {
                        result = result + specialNums[0];
                        i--;
                    } else if (current.equals("D") && next.equals("C")) {
                        result = result + specialNums[1];
                        i--;
                    } else if (current.equals("C") && next.equals("X")) {
                        result = result + specialNums[2];
                        i--;
                    } else if (current.equals("L") && next.equals("X")) {
                        result = result + specialNums[3];
                        i--;
                    } else if (current.equals("X") && next.equals("I")) {
                        result = result + specialNums[4];
                        i--;
                    } else if (current.equals("V") && next.equals("I")) {
                        result = result + specialNums[5];
                        i--;
                    } else {
                        result = result + nums[i1];
                    }
                    break;
                }
            }
        }

        return result;
    }

    /**
     * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
     * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/integer-to-roman
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 MCMXCIV
     *
     * @param num
     * @return
     */
    public static String intToRoman(int num) {
        int m = 0, d = 0, c = 0, l = 0, x = 0, v = 0, i = 0;
        int cm = 0;//cm 900
        int cd = 0;//CD
        int xc = 0;//XC 90
        int xl = 0;//XL
        int ix = 0;//IX 9
        int iv = 0;//IV
        m = num / 1000;
        int left = num - m * 1000;
        if (left / 900 > 0) {
            cm = left / 900;
            left = left - 900 * cm;
        } else {
            d = left / 500;
            left = left - 500 * d;
        }

        if (left / 400 > 0) {
            cd = left / 400;
            left = left - 400 * cd;
        } else {
            c = left / 100;
            left = left - 100 * c;
        }

        if (left / 90 > 0) {
            xc = left / 90;
            left = left - 90 * xc;
        } else {
            l = left / 50;
            left = left - 50 * l;
        }

        if (left / 40 > 0) {
            xl = left / 40;
            left = left - 40 * xl;
        } else {
            x = left / 10;
            left = left - 10 * x;
        }

        if (left / 9 > 0) {
            ix = left / 9;
            left = left - 9 * ix;
        } else {
            v = left / 5;
            left = left - 5 * v;
        }

        if (left / 4 > 0) {
            iv = left / 4;
        } else {
            i = left;
        }
        String[] display = new String[]{"M", "CM", "CD", "D", "C", "XC", "XL", "L", "X", "V", "IX", "IV", "I"};

        int[] values = new int[]{m, cm, cd, d, c, xc, xl, l, x, v, ix, iv, i};
        String result = "";
        for (int i1 = 0; i1 < values.length; i1++) {
            for (int i2 = 0; i2 < values[i1]; i2++) {
                result = result + display[i1];
            }
        }
        return result;
    }


}